Recherche de plus court chemin
Cette activité propose de travailler sur la résolution des labyrinthes. Pour cela, on va réutiliser le travail de modélisation et de visualisation des labyrinthes effectué lors cette activité préliminaire (il est plus que recommandé de l'avoir faite avant de commencer l'activité présente) : Génération de labyrinthe en Python. Visualisation 2d et 3d. Si besoin, vous pouvez télécharger ici la classe Labyrinthe nécessaire pour démarrer cette activité. Au travers d'exercices guidés, nous réaliserons les objectifs suivants :
  • Mise en place d' algorithmes de parcours d'un labyrinthe
  • Affiner les algorithmes pour trouver les plus courts chemins
  • Implémentation en Python de l'algorithme de résolution
  • Représentation 2D de la solution en utilisant la librairie matplotlib de Python.
  • Représentation 3D de la solution en utilisant une libriairie JavaScript.
Nous nous intéressons ici à résoudre un labyrinthe rectangulaire. Dans un premier temps nous parcourrons des labyrinthes parfaits, puis plus généraux. Ces notions sont déjà introduites dans l'activité génération d'un labyrinthe. Nous allons réfléchir à des méthodes algorithmiques pour parcourir un labyrinthe. Parcourir un labyrinthe consiste, en partant d'une cellule initiale, à explorer l'ensemble total des cellules du labyrinthe. L'objectif de cette partie est de définir deux algorithmes de parcours de labyrinthe (appelés parcours en profondeur et en largeur). Nous devons fixer le contexte dans lequel nous nous plaçons car résoudre un labyrinthe imprimé dans un magasine ne se fait pas de la même manière qu'en déambulant dans un labyrinthe réel sans carte... Nous choisissons un cadre assez contraignant pour explorer les cellules d'un labyrinthe donné :
  • on n'a pas de vue globale du labyrinthe, on doit se déplacer pour connaître les cellules.
  • on ne peut observer que la cellule sur laquelle on se trouve ainsi que les voisines directes (4 au plus)
  • on peut tenir une carte des cellules déjà dévoilées et y revenir à n'importe quelle étape
  • on peut laisser une ou plusieurs marques (valeur, message simple, signe,...) dans une cellule dévoilée
De plus, on doit essayer lors du parcours de ne pas se perdre et d'éviter les aller-retour inutiles... Afin de se mettre dans les conditions, le petit labyrinthe interactif ci-dessous propose de parcourir un labyrinthe "sans visibilité", c'est à dire en ne pouvant observer que les cellules voisines. Il reste possible de se "souvenir" des cases apperçues, mais non visitées. La cellule active est déplaçable. On apperçoit les voisins immédiats en blanc. Pour les déplacement on peut utiliser les flèches directionnelles ou directement en cliquant sur une case connue :

A partir de cet exemple, on va tenter de mettre en place une ébauche d'algorithme pour le parcours d'un labyrinthe : Afin de décrire une stratégie d'exploration ou plutôt une ébauche d'algorithme, on pourra utiliser les notations suivantes :
  • C : la cellule actuelle. C' : une autre cellule
  • a_visiter : une liste de cellules à visiter à garder en mémoire
  • l'action visiter(C') pour explorer la cellule C' (qui devient C)
  • voisins(C) : fonction qui renvoie la liste des voisins immédiats de C
  • la possibilité de choisir une cellule en expliquant comment
  • Toute autre variable ou action précise jugée pertinente...
Il existe plusieurs manières de choisir l'ordre dans lequel on explore les cellules : Parcourir le labyrinthe en profondeur, c'est à dire en explorant un chemin jusqu'à arriver dans une impasse avant de revenir en arrière. Proposer un algorithme décrivant cette approche. Parcourir le labyrinthe en largeur, c'est à dire de manière plus prudente, en explorant en premier les cellules les moins éloignées du départ avant d'aller plus loin. Proposer un algorithme décrivant cette approche.
  • Ajouter dans la liste a_visiter les nouvelles cellules voisines rencontrées.
  • Continuer de parcourir le labyrinthe tant que la liste a_visiter n'est pas vide.
  • Retirer la cellule C de la liste a_visiter lorsqu'elle est visitée.
Les algorithmes précédents sont adaptés aux labyrinthes parfaits, mais pas vraiment aux labyrinthes plus généraux. Essayez de parcourir le labyrinthe suivant pour vous en persuader :

Quel défaut présentent nos deux algorithmes précédents sur un labyrinthe non parfait ? En vous inspirant de la marque jaune laissée dans l'exemple précédent à chaque déplacement, proposez une solution qui évite les boucles dans les parcours en profondeur et en largeur. Indice 1-a Essayer de parcourir entièrement le labyrinthe imparfait... Indice 1-b ... les algorithmes de parcours vont-ils s'arrêter ? (ajout des voisins) Indice 2-a Utiliser un liste visitees dans laquelle on mémorise les cellules déjà visitées Indice 2-b Au départ la liste est vide car aucune cellule n'est visitée Indice 2-c Ne surtout pas ajouter un voisin déjà visité ! Dans cette partie, nous adapterons les algorithmes précédents afin de connaître les distances parcourues pour atteindre chaque cellule depuis le départ. On raisonnera pour l'instant sur des labyrinthes parfaits uniquement. Essayez de parcourir le labyrinthe ci-dessous en notant la distance parcourue jusqu'à chaque nouvelle cellule dévoilée avec le crayon :

Pour un algorithme de parcours, et pour pour toute cellule C du labyrinthe, on notera dC la distance parcourue pour atteindre C à partir de la cellule de départ. En adaptant les algorithmes précédent : proposer un algorithme qui calcule les distances dC avec un parcours en profondeur proposer un algorithme qui calcule les distances dC avec un parcours en largeur En appliquant les deux méthodes sur l'exemple ci-dessus, obtient-on les mêmes valeurs pour les distances dC ? Sachant qu'on applique nos algorithmes sur des labyrinthes parfaits, est-il possible de faire mieux , c'est à dire d'atteindre chaque cellule C en moins de déplacements que dC ? Justifier et commenter la question précédente. Indice 1-a Au début, toutes les valeurs dC' sont infinies (car C' pas visitées) sauf pour cellule de départ C où dC=0 Indice 1-b Chaque fois qu'on dévoile un voisin C' de C, il est à distance dC+1 car à côté de C Indice 1-c Attention, si la valeur dC' est déjà plus petite que dC+1, on ne doit pas la changer... Indice 1-d Les valeurs dC se calculent de la même manière en largeur ou en profondeur. Indice 2 On dirait bien Indice 3 Dans un labyrinthe parfait, deux cellules sont toujours reliées par un chemin unique L'exemple traité avant était particulier car un seul chemin était possible pour atteindre une cellule. Quand ça n'est pas le cas, il y a nécessairement un (ou plusieurs) plus court(s) chemin(s) L'objectif de cette partie est de mettre en place un algorithme calculant les plus petites distances pour atteindre une cellule dans un labyrinthe rectangulaire quelconque. Cela nous permettra de trouver les plus cours chemins depuis la cellule de départ. Vous pouvez essayer de parcourir de différentes manières le labyrinthe ci-dessous :

Après avoir essayé plusieurs parcours sur l'exemple ci-dessus, le parcours en profondeur semble-t'il être une bonne manière pour calculer les plus petites distances au point de départ ? Expliquer. Essayer à nouveau de parcourir le labyrinthe de l'exemple, mais en largeur. Si dans l'exemple on change l'ordre de priorité des cellules voisines (par exemple "gauche", "droite", "haut", "bas" au lieu de "haut", "bas", "gauche", "droite"), que remarque-t'on concernant les valeurs dC calculées ? Nous allons essayer de simplifier l'algorithme du parcours en largeur pour nous passer de la liste visitees. On initialisera a_visiter avec toutes les cellules sauf celle de départ. Comment faire pour choisitr la plus ancienne cellule dévoilée dans a_visiter ? Proposer une modification du parcours en largeur qui tient compte de la question précédente. Indice 1 Essayer d'atteindre un coin en partant vers la droite... puis recommencer en partant vers la gauche. Indice 2-a A chaque étape, les voisins C' quand on les ajoute, ont la même valeur dC... Indice 2-b A quel moment ont été ajoutées les cellules avec le plus petit dC ? Le plus grand ? Indice 2-c Une cellule est visitée si elle n'est pas dans a_visiter. Il n'y plus besoin d'ajouter les voisins à chaque étape. On admet que l'algorithme précédent calcule effectivement les distances minimales des chemins reliant les cellules à celle de départ. Nous avons les distances minimales, mais pas encore les chemins les plus courts. Comme il est possible de laisser une information dans une cellule dévoilée, on peut par exemple y marquer la cellule précédente :

Pour toute cellule C, on notera predC la cellule qui lui précède dans le parcours. En s'inspirant de l'exemple précédent, proposer un algorithme qui prend deux cellules C et D du labyrinthe et calcule le chemin le plus court pour aller de C à D. Indice 1 On départ, les valeurs predC sont non définies car aucun parcours Indice 2 A chaque fois qu'on calcule une valeur dC', on sait que C précède C' Indice 3 Pour trouver le chemin minimal entre C et D, on peut partir de D et reculer...
Nous réutiliserons dans cette partie la classe Labyrinthe créée précédemment. Au besoin, vous pouvez télécharger cette version. L'objectif principal qui est d'implémenter l'algorithme de recherche du plus court chemin ou algorithme de Dijkstra, sera divisé plusieurs objectifs intermédiaires :
  • Initialisation des attributs nécessaire à la résolution : liste de noeuds restants a_visiter, tableau des distances parcourues et tableau des predecesseurs.
  • Une méthode de calcul des voisins()
  • Une méthode de mise à jour des distances parcourues MAJ_distances()
  • Une méthode de choix de la cellule suivante choix_cellule()
  • Et finalement l'algorithme de parcours dijkstra()

On rappelle qu'on se place dans le cadre d'un labyrinthe rectangulaire de dimensions width colonnes par height lignes. Ecrire une méthode Labyrinthe.init_dijkstra(i0,j0) qui prend en arguments i0 et j0 les coordonnées de la cellule de départ et qui crée les attributs suivants (qui sont tous des ) :
  • Labyrinthe.a_visiter une liste de couples de coordonnées[[i1,j1],..., [ik,jk]] restant à visiter lors du parcours.Initialement, toutes les cellules du labyrinthe sont à visiter.
  • Labyrinthe.distances un tableau de height lignes par height colonnes. Chaque élément du tableau de coordonnée (i,j) est un entier indiquant le nombre déplacements entre la cellule (i,j) et la cellule de départ. La valeur initiale est ∞ (car les cellules ne sont pas atteintes).
 Indice 1 L'infini est représenté par float("inf") Indice 2 distances est des tableaux à height lignes et heightcolonnes Indice 3 a_visiter est une liste (vide au début) qui contient des couples (i,j) de coordonnées de cellules Indice 4 Choisir des coordonnés impossibles pour indiquer l'absence de prédécesseur Afin de visualiser les attributs dans les labyrinthes générés, nous pouvons utiliser la méthode self.print(valeurs). Il faut modifier la méthode afin de lui permettre d'afficher les distances. On peut recopier la méthode ci-dessous ou la télécharger. Télécharger la méthode Labyrinthe.print.py def print(self, labels=False): from math import floor #alias : w=self.width;h=self.height;c=self.cells; #si on imprime les labels, il faut élargir la taille des couloirs if(labels==True): labels=[ [ c[i][j]['zone'] for i in range(h) ] for j in range(w) ] if(labels): len_lbl=max([ max([ len(str(labels[i][j])) for i in range(h) ]) for j in range(w) ])+1 inters=[' ','╴','╷', '┐','╶','─','┌','┬','╵','┘','│','┤','└','┴','├','┼'] t="" #la grille des intersections de cases est de taille (N+1)(M+1) for i in range(h+1): interligne="" for j in range(w+1): #up, right, bottom, left : les 4 parties de la croix "┼" #False = mur, True = pas mur #Coins et bords: up=False if i==0 else None left=False if j==0 else None right=False if j==w else None bottom=False if i==h else None if j==w: if up==None:up=not c[i-1][j-1]['E'] if bottom==None:bottom=not c[i][j-1]['E'] if i==h: bottom=False if right==None:right=not c[i-1][j]['S'] if left==None:left=not c[i-1][j-1]['S'] #intérieur : if up==None:up=not c[i-1][j]['W'] if right==None:right=not c[i][j]['N'] if bottom==None:bottom=not c[i][j]['W'] if left==None:left=not c[i][j-1]['N'] #-> mot binaire à 4 bits. 16 cas qu'on a mis dans l'ordre dans la liste inters #indice inters k=-up*8+right*4+bottom*2+left if not labels: #espacement horizontal supplémentaire sep= "─" if left else " " t+=sep+inters[k] if j==self.width:t+="\n" else: sep= (len_lbl+2)*"─" if right else (len_lbl+2)*" " lbl=labels[i][j] if i<self.height and j<self.width else "" len_sp_left=floor((len_lbl - len(str(lbl)))/2) len_sp_right=len_lbl-len(str(lbl))-len_sp_left txt_lbl=str(lbl) interligne+=("│" if bottom else " ")+" "*(len_sp_left+1)+txt_lbl+" "*(len_sp_right+1) t+=inters[k]+sep if j==self.width: t+="\n" + interligne + "\n" print(t) Cette méthode permet de vérifier que notre méthode init_dijkstra() fonctionne correctement en affichant les attributs self.distances : laby = new Labyrinthe(3,3) >>>laby.print(laby.cellules_visitees) ┌──────┬─────────────┐ │ inf │ inf inf │ │ ╵ ╶──────┤ │ inf inf inf │ ├──────╴ ╶──────┤ │ inf inf inf │ └────────────────────┘ Dans le déroulement de l'algorithme on a besoin à chaque étape de connaître les coordonnées des cellules voisines : Ecrire une méthode Labyrinthe.voisins(i,j) qui prend en arguments i et j les coordonnées d'une cellule et qui renvoie une liste de couples de coordonnées[(i1,j1),..., (ik,jk)] de voisins directs (4 maximum) : Indice 1 Utiliser les attributs N,E,S,W de la cellule de coordonnées (i,j) pour connaître ses voisins Indice 2 Attention aux bords qui n'ont pas de voisins... Indice 3 On peut utiliser une boucle for k in D: pour parcourir les clé d'un dictionnaire D Afin de passer à l'étape suivante, il est nécessaire de mettre à jour les distances des voisins de la cellule actuelle Ecrire une méthode Labyrinthe.MAJ_distances(i1,j1) qui prend en arguments i1 et j1 les coordonnées d'une cellule à une étape de l'algorithme et qui pour chaque cellule voisine i,j affecte à sa distance celle du prédécesseur i1,j1 augmentée de 1 à la condition que cette nouvelle distance améliore l'ancienne (plus courte). Indice 1 Parcourir les voisins (i2,j2) de (i1,j1) et actualiser distances[i2][j2] si besoin Indice 2 Pour parcourir une liste L de couples (i,j), on peut utiliser for (i,j) in L: L'étape clé de l'algorithme pour passer à l'étape suivante est de bien choisir sélectionner la cellules de l'étape suivante, c'est à dire celle qui a la plus courte distance au point de départ (pour l'instant) : Ecrire une méthode Labyrinthe.choix_chemin() qui recherche dans les cellules de l'attribut Labyrinthe.a_visiter celle qui a la distance calculée la plus petite (afin de la sélectionner dans l'algorithme de parcours). Indice 1 Parcourir les cellules (i,j) de a_visiter pour trouver la plus petite distances[i][j] Indice 2 utiliser une variable dmin (plus petite distance) et (imin,jmin) la cellule correspondante. Indice 3 Au départ, dmin est très très grande, et imin et jmin indéfinis Les méthodes nécessaires à la progression dans le parcours et les attributs permettant de représenter les informations importantes sont en place. Reste à parcourir le labyrinthe en largeur en marquant les distances tout en choisissant les bonnes cellules suivantes : Ecrire une méthode Labyrinthe.dijkstra(i0,j0) qui prend en arguments i0 et j0 la cellule de départ et qui parcourt le labyrinthe en largeur pour trouver les distances minimales de chaque cellule à celle de départ. Indice 1 Utiliser dans le bon ordre les méthodes précédentes Indice 2 Itérer Tant que a_visiter n'est pas vide Indice 3 Au départ, dmin est très très grande, et imin et jmin indéfinis Vérifier à l'aide de Labyrinthe.print(), en affichant les distances, que le parcours se déroule correctement : ┌─────┬───────────┬───────────┐ │ 0 │ 13 12 │ 15 14 │ │ ├─────┐ └─────╴ │ │ 1 │ 4 │ 11 12 13 │ │ ╵ │ ╶─────┐ │ │ 2 3 │ 10 9 │ 14 │ │ ┌─────┘ ╷ └─────┤ │ 3 │ 12 11 │ 8 9 │ │ └───────────┘ ╶─────┤ │ 4 5 6 7 8 │ └─────────────────────────────┘ Enfin, pour deux cellules données, un départ i0,j0 et une arrivée iN,jN, on souhaite afficher le chemin le plus court les reliant :
  • Ecrire une méthode Labyrinthe.court_chemin(i0,j0,iN,jN) qui prend en arguments i0, j0 la cellule de départ et iN, jN et renvoie le plus court chemin dans le parcours de dijkstra(), c'est à dire la liste des cellules composant ce chemin.
  • Ecrire une méthode Labyrinthe.print_chemin(i0,j0,iN,jN) qui affiche dans la console le plus court chemin entre les cellules données en argument de la manière suivante : ┌────┬────┬──────────────┬────┬────┬────┬────┬────┬─────────┬──────────────┐ │ * │ │ │ │ │ │ │ │ │ │ │ ╵ └────╴ ╷ │ ╵ │ │ │ ╵ ╶────┤ ╶────┐ │ │ * * │ │ │ │ │ │ │ │ │ ╷ ╶────┐ └────┘ ┌────┤ ╵ │ ╷ ╶────┴────╴ │ │ │ │ * * │ │ │ │ │ │ │ ├────┼────╴ │ ╷ ┌────┘ ╵ ╷ └────┤ ╷ ┌─────────┴────┤ │ │ * │ │ │ │ * * │ │ │ │ │ │ ╷ └────┴────┼────╴ ┌────┘ ╷ ╵ ├────┘ ╷ ╶────┤ │ │ │ * │ │ * │ * * │ │ │ │ ╵ │ ╷ ╷ └────┬────┼────╴ └────┐ ╵ ╶────┤ ╶────┤ │ │ * │ │ │ │ * * │ * * * │ │ │ ╶────┤ └────┼────┐ │ │ ╶─────────┼─────────╴ │ ╶────┤ │ │ * │ │ │ │ * │ * │ │ ├────╴ │ ╶────┘ │ │ ╵ ╶────┬────┴────┬────╴ ├────┐ │ │ │ * * * │ │ * * │ │ * │ │ │ ├────╴ └────┬────╴ └────┘ ┌────┬────┼────╴ └────╴ ╵ │ │ │ │ * * * │ │ │ * * │ │ ├────┬────╴ │ ┌────┐ ┌────┘ ╵ ├────╴ ┌─────────╴ └────┤ │ │ │ │ │ │ │ │ * │ │ │ ╷ │ ╵ │ ╵ ╶────┐ │ ┌────┘ ┌────┐ ┌────┤ │ │ │ │ │ │ │ │ │ │ * │ │ │ │ └────┼─────────┼─────────╴ ├────┴────┘ ┌────┤ │ ╵ │ │ │ │ │ │ │ │ │ * │ │ └─────────┴────┐ └────┐ ╶────┼────┐ ╷ ╵ ╵ │ ╶────┤ │ │ │ │ │ │ │ * * │ │ ╶────┐ ┌────┘ ╶────┘ ╷ │ ╵ └────┬────╴ ├────╴ │ │ │ │ │ │ │ │ * * │ │ ╶────┤ ╵ ╷ ┌────╴ ├────┘ ╷ ╷ └────┐ │ ╶────┤ │ │ │ │ │ │ │ │ │ * * │ └─────────┴─────────┴────┴─────────┴─────────┴────┴─────────┴────┴─────────┘
  • Afin de retrouver le chemin de n'importe quelle cellule i,j à la cellule de départ i0,j0, il suffit de noter la cellule précedente dans un tableau height par width qu'on appelera predecesseurs. En remontant les prédécesseurs, on arrive toujours à la cellule de départ en parcourant le chemin à l'envers.
  • L'attribut predecesseurs doit être initialisé dans init_dijkstra() puis mis à jour à chaque itération dans MAJ_distances(). A l'initialisation, les cellules n'ont aucun prédecesseur, la valeur par défaut pourra être (None, None) ou (-1,-1).
Jusqu'ici, nous n'avons testé l'algorithme de Dijkstra sur des labyrinthes parfaits. Le plus court chemin est donc le seul chemin...
  • Créer une méthode Labyrinthe.ouvrir_murs(pct) qui prend en argument un pourcentage (nombre entre 0 et 100) et qui ouvre aléatoirement pct %des murs dans le labyrinthe.
  • Tester les méthodes précédentes sur des labyrinthes imparfaits.
┌────────────────────────┐ │ * * │ ├────╴ ┌────╴ │ │ * │ │ │ ╷ ╶────┴────╴ │ │ │ * * * │ │ └────┬────┐ ╶────┤ │ │ │ * * │ │ ╷ ╵ └────┐ │ │ │ │ * │ └────┴──────────────┴────┘ Indice 1 Il y a height*width cellules. Pour arrondir un nombre, utiliser la fonction int(). Indice 2 Tirer un entier au hasard entre a et b inclus se fait avec random.randint(a,b) Indice 3 Il n'est pas nécessaire utile d'être précis au point de vérifier si les murs qu'on ouvre sont fermés...
Dans cette partie, nous allons réutiliser la librairie matplotlib.pyplot et compléter la méthode print_plot() afin de tracer graphiquement le chemin le plus court reliant deux cellules. Modifier la méthode Labyrinthe.print_plot(chemin) qui prendra désormais un argument facultatif chemin (obtenu par court_chemin(i0,j0,i1,j1)). Permettant d'afficher le chemin, lorsqu'il est précisé, de la manière suivante : Dans cette partie, nous réutilisons la librairie JavaScript que nous avions utilisé dans le TD précédent pour visualiser en 3D les labyrinthes générés. Nous tracer la solution du labyrinthe sous la forme d'un fil d'ariane, de points visuels ou de tout autre indice visuel permettant de suivre le chemin jusqu'à la sortie.

Au besoin, vous pouvez partir de cette archive . Le fichier labyrinthe.js contient les instructions qui mettent en scène un labyrinthe. La fichier labyrinthe.html est à ouvrir dans le navigateur.

A partir des cellules cells d'un labyrinthe généré, ainsi que d'un chemin solution (liste de coordonnées de cellules), modifier votre fichier labyrinthe.js afin de faire apparaître le chemin solution. Le choix de l'indice visuel est laissé à votre discrétion (pierres au sol, flèche sur le mur, fil suspendu, etc.)